Optimization, Complexity and Invariant Theory (Invited Talk)

Author Peter Bürgisser



PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.1.pdf
  • Filesize: 0.78 MB
  • 20 pages

Document Identifiers

Author Details

Peter Bürgisser
  • Institut für Mathematik, Technische Universität Berlin, Germany

Acknowledgements

The talk (and this write-up) are mainly based on the joint articles [Peter Bürgisser et al., 2019, https://doi.org/10.1109/FOCS.2019.00055; Peter Bürgisser et al., 2019, https://arxiv.org/abs/1910.12375] with Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter and Avi Wigderson. I am grateful to my coauthors for inspiration and enlightening discussions and thank Levent Dogan, Yinan Li, Visu Makam, Harold Nieuwboer and Philipp Reichenbach for valuable feedback.

Cite AsGet BibTex

Peter Bürgisser. Optimization, Complexity and Invariant Theory (Invited Talk). In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.1

Abstract

Invariant and representation theory studies symmetries by means of group actions and is a well established source of unifying principles in mathematics and physics. Recent research suggests its relevance for complexity and optimization through quantitative and algorithmic questions. The goal of the talk is to give an introduction to new algorithmic and analysis techniques that extend convex optimization from the classical Euclidean setting to a general geodesic setting. We also point out surprising connections to a diverse set of problems in different areas of mathematics, statistics, computer science, and physics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Continuous optimization
Keywords
  • geometric invariant theory
  • geodesic optimization
  • non-commutative optimization
  • null cone
  • operator scaling
  • moment polytope
  • orbit closure intersection
  • geometric programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Pierre-Antoine Absil, Robert E. Mahony, and Rodolphe Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008. URL: http://press.princeton.edu/titles/8586.html.
  2. Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 172-181. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188942.
  3. Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 890-901. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.87.
  4. Carlos Améndola, Kathlén Kohn, Philipp Reichenbach, and Anna Seigal. Invariant theory and scaling algorithms for maximum likelihood estimation, 2020. URL: http://arxiv.org/abs/2003.13662.
  5. Michael F Atiyah. Convexity and commuting Hamiltonians. Bulletin of the London Mathematical Society, 14(1):1-15, 1982. URL: https://doi.org/10.1112/blms/14.1.1.
  6. Velleda Baldoni, Michèle Vergne, and M. Walter. Computation of dilated Kronecker coefficients. J. Symb. Comput., 84:113-146, 2018. URL: https://doi.org/10.1016/j.jsc.2017.03.005.
  7. Prakash Belkale and Shrawan Kumar. Eigenvalue problem and a new product in cohomology of flag varieties. Inventiones mathematicae, 166:185-228, 2006. URL: https://doi.org/10.1007/s00222-006-0516-x.
  8. Arkady Berenstein and Reyer Sjamaar. Coadjoint orbits, moment polytopes, and the Hilbert-Mumford criterion. Journal of the American Mathematical Society, 13(2):433-466, 2000. URL: https://doi.org/10.1090/S0894-0347-00-00327-1.
  9. Nicole Berline, Michèle Vergne, and Michael Walter. The Horn inequalities from a geometric point of view. L'Enseignement Mathématique, 63:403-470, 2017. URL: http://arxiv.org/abs/1611.06917.
  10. Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2014. URL: https://doi.org/10.1017/CBO9780511804441.
  11. Michel Brion. Sur l'image de l'application moment. In Séminaire d'algebre Paul Dubreil et Marie-Paule Malliavin, volume 1296 of Lecture Notes in Mathematics, pages 177-192. Springer, 1987. Google Scholar
  12. Peter Bürgisser, Matthias Christandl, Ketan D. Mulmuley, and Michael Walter. Membership in moment polytopes is in NP and coNP. SIAM J. Comput., 46(3):972-991, 2017. URL: https://doi.org/10.1137/15M1048859.
  13. 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. CoRR, abs/1804.04739, 2018. URL: http://arxiv.org/abs/1804.04739.
  14. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Towards a theory of non-commutative optimization: Geodesic 1st and 2nd order methods for moment maps and polytopes. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 845-861. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00055.
  15. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. CoRR, abs/1910.12375, 2019. URL: http://arxiv.org/abs/1910.12375.
  16. Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 24:1-24:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.24.
  17. Peter Bürgisser and Christian Ikenmeyer. Deciding positivity of Littlewood-Richardson coefficients. SIAM J. Discret. Math., 27(4):1639-1681, 2013. URL: https://doi.org/10.1137/120892532.
  18. Peter Bürgisser, Yinan Li, Harold Nieuwboer, and Michael Walter. Interior-point methods for unconstrained geometric programming and scaling problems, 2020. URL: http://arxiv.org/abs/2008.12110.
  19. Matthias Christandl, Brent Doran, Stavros Kousidis, and Michael Walter. Eigenvalue distributions of reduced density matrices. Communications in Mathematical Physics, 332(1):1-52, 2014. URL: https://doi.org/10.1007/s00220-014-2144-4.
  20. Matthias Christandl, Brent Doran, and Michael Walter. Computing multiplicities of Lie group representations. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 639-648. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.43.
  21. Matthias Christandl, Aram W Harrow, and Graeme Mitchison. Nonzero Kronecker coefficients and what they tell us about spectra. Communications in Mathematical Physics, 270(3):575-585, 2007. URL: https://doi.org/10.1007/s00220-006-0157-3.
  22. Matthias Christandl and Graeme Mitchison. The spectra of quantum states and the Kronecker coefficients of the symmetric group. Communications in Mathematical Physics, 261(3):789-797, 2006. URL: https://doi.org/10.1007/s00220-005-1435-1.
  23. 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 Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 902-913. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.88.
  24. Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint. Trust Region Methods. MOS-SIAM Series on Optimization. SIAM, 2000. URL: https://doi.org/10.1137/1.9780898719857.
  25. Sumit Daftuar and Patrick Hayden. Quantum state transformations and the Schubert calculus. Annals of Physics, 315(1):80-122, 2005. URL: https://doi.org/10.1016/j.aop.2004.09.012.
  26. Harm Derksen and Gregor Kemper. Computational invariant theory. Springer, 2015. Google Scholar
  27. Harm Derksen and Visu Makam. Polynomial degree bounds for matrix semi-invariants. Advances in Mathematics, 310:44-63, 2017. URL: https://doi.org/10.1016/j.aim.2017.01.018.
  28. Harm Derksen and Visu Makam. Algorithms for orbit closure separation for invariants and semi-invariants of matrices, 2018. URL: http://arxiv.org/abs/1801.02043.
  29. Harm Derksen and Visu Makam. Maximum likelihood estimation for matrix normal models via quiver representations, 2020. URL: http://arxiv.org/abs/2007.10206.
  30. Harm Derksen, Visu Makam, and Michael Walter. Maximum likelihood estimation for tensor normal models via Castling transforms, 2020. URL: http://arxiv.org/abs/2011.03849.
  31. Harm Derksen and Jerzy Weyman. An introduction to quiver representations, volume 184. American Mathematical Society, 2017. Google Scholar
  32. Mathias Drton, Satoshi Kuriki, and Peter Hoff. Existence and uniqueness of the Kronecker covariance MLE, 2020. URL: http://arxiv.org/abs/2003.06024.
  33. Michael A. Forbes and Amir Shpilka. Explicit noether normalization for simultaneous conjugation via polynomial identity testing. Electron. Colloquium Comput. Complex., 20:33, 2013. URL: http://eccc.hpi-web.de/report/2013/033.
  34. Cole Franks. Operator scaling with specified marginals. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 190-203. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188932.
  35. Cole Franks and Philipp Reichenbach. Barriers for recent methods in geodesic optimization. Preprint, 2020. URL: http://arxiv.org/abs/2102.06652.
  36. William Fulton. Eigenvalues, invariant factors, highest weights, and Schubert calculus. Bulletin of the American Mathematical Society, 37(3):209-249, 2000. URL: http://arxiv.org/abs/math/9908012.
  37. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 109-117. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.95.
  38. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. Algorithmic and optimization aspects of brascamp-lieb inequalities, via operator scaling. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 397-409. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055458.
  39. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. Operator scaling: Theory and applications. Found. Comput. Math., 20(2):223-290, 2020. URL: https://doi.org/10.1007/s10208-019-09417-z.
  40. Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Search problems in algebraic complexity, GCT, and hardness of generators for invariant rings. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 12:1-12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.12.
  41. V. Guillemin and S. Sternberg. Convexity properties of the moment mapping. Inventiones mathematicae, 67:491-513, 1982. Google Scholar
  42. Leonid Gurvits. Classical complexity and quantum entanglement. J. Comput. Syst. Sci., 69(3):448-484, 2004. URL: https://doi.org/10.1016/j.jcss.2004.06.003.
  43. Leonid Gurvits. Combinatorial and algorithmic aspects of hyperbolic polynomials. Electron. Colloquium Comput. Complex., (070), 2004. URL: http://eccc.hpi-web.de/eccc-reports/2004/TR04-070/index.html.
  44. Leonid Gurvits. Hyperbolic polynomials approach to van der waerden/schrijver-valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 417-426. ACM, 2006. URL: https://doi.org/10.1145/1132516.1132578.
  45. Leonid Gurvits and Peter N. Yianilos. The deflation-inflation method for certain semidefinite programming and maximum determinant completion problems. Technical Report, NECI, 1998. Google Scholar
  46. Linus Hamilton and Ankur Moitra. The paulsen problem made simple. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 41:1-41:6. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.41.
  47. David Hilbert. Über die vollen Invariantensysteme. Math. Ann., 42:313-370, 1893. Google Scholar
  48. Christian Ikenmeyer, Ketan D. Mulmuley, and Michael Walter. On vanishing of Kronecker coefficients. Comput. Complex., 26(4):949-992, 2017. URL: https://doi.org/10.1007/s00037-017-0158-y.
  49. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Constructive non-commutative rank computation is in deterministic polynomial time. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 55:1-55:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.55.
  50. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Non-commutative Edmonds' problem and matrix semi-invariants. Comput. Complex., 26(3):717-763, 2017. URL: https://doi.org/10.1007/s00037-016-0143-x.
  51. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex., 13(1-2):1-46, 2004. URL: https://doi.org/10.1007/s00037-004-0182-6.
  52. Narendra Karmarkar. A new polynomial-time algorithm for linear programming. Comb., 4(4):373-396, 1984. URL: https://doi.org/10.1007/BF02579150.
  53. George Kempf and Linda Ness. The length of vectors in representation spaces. In Algebraic geometry, pages 233-243. Springer, 1979. Google Scholar
  54. Leonid G Khachiyan. A polynomial algorithm in linear programming. In Doklady Academii Nauk SSSR, volume 244, pages 1093-1096, 1979. Google Scholar
  55. Frances Kirwan. Convexity properties of the moment mapping, III. Inventiones mathematicae, 77(3):547-552, 1984. Google Scholar
  56. Frances Clare Kirwan. Cohomology of quotients in symplectic and algebraic geometry, volume 31. Princeton University Press, 1984. Google Scholar
  57. Alexander Klyachko. Quantum marginal problem and representations of the symmetric group, 2004. URL: http://arxiv.org/abs/quant-ph/0409113.
  58. Alexander A Klyachko. Stable bundles, representation theory and hermitian operators. Selecta Mathematica, New Series, 4(3):419-445, 1998. URL: https://doi.org/10.1007/s000290050037.
  59. A Knutson and T Tao. The honeycomb model of GL_n(ℂ) tensor products I: Proof of the saturation conjecture. Journal of the American Mathematical Society, 12(4):1055-1090, 1999. URL: http://arxiv.org/abs/math/9807160.
  60. B. Kostant. On convexity, the Weyl group and the Iwasawa decomposition. Ann. scient. E.N.S, 6:413-455, 1973. Google Scholar
  61. V. M. Kravtsov. Combinatorial properties of noninteger vertices of a polytope in a three-index axial assignment problem. Cybernetics and Systems Analysis, 43(1):25-33, 2007. Google Scholar
  62. Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, and Akshay Ramachandran. The Paulsen problem, continuous operator scaling, and smoothed analysis. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 182-189. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188794.
  63. Nathan Linial, Alex Samorodnitsky, and Avi Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 644-652. ACM, 1998. URL: https://doi.org/10.1145/276698.276880.
  64. Jesús A. De Loera and Tyrrell B. McAllister. On the computation of Clebsch-Gordan coefficients and the dilation effect. Exp. Math., 15(1):7-19, 2006. URL: https://doi.org/10.1080/10586458.2006.10128948.
  65. Visu Makam and Avi Wigderson. Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties). CoRR, abs/1909.00857, 2019. URL: http://arxiv.org/abs/1909.00857.
  66. Ketan Mulmuley. Geometric complexity theory V: equivalence between blackbox derandomization of polynomial identity testing and derandomization of noether’s normalization lemma. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 629-638. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.15.
  67. Ketan Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. Journal of the American Mathematical Society, 30(1):225-309, 2017. URL: http://arxiv.org/abs/1209.5993.
  68. Ketan D Mulmuley, Hariharan Narayanan, and Milind Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. Journal of Algebraic Combinatorics, 36(1):103-110, 2012. Google Scholar
  69. David Mumford. Geometric invariant theory. Springer-Verlag, 1965. Google Scholar
  70. Linda Ness and David Mumford. A stratification of the null cone via the moment map. American Journal of Mathematics, 106(6):1281-1329, 1984. URL: https://doi.org/10.2307/2374395.
  71. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Comput. Complex., 14(1):1-19, 2005. URL: https://doi.org/10.1007/s00037-005-0188-8.
  72. Nicolas Ressayre. Geometric invariant theory and the generalized eigenvalue problem. Inventiones mathematicae, 180(2):389-441, 2010. URL: https://doi.org/10.1007/s00222-010-0233-3.
  73. Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport. SIAM J. Optim., 29(2):1444-1472, 2019. URL: https://doi.org/10.1137/17M1116787.
  74. Mohit Singh and Nisheeth K. Vishnoi. Entropy, optimization and counting. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 50-59. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591803.
  75. Damian Straszak and Nisheeth K. Vishnoi. Maximum entropy distributions: Bit complexity and stability. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 2861-2891. PMLR, 2019. URL: http://proceedings.mlr.press/v99/straszak19a.html.
  76. Bernd Sturmfels. Algorithms in Invariant Theory. Texts & Monographs in Symbolic Computation. Springer, 2008. URL: https://doi.org/10.1007/978-3-211-77417-5.
  77. Constantin Udriste. Convex functions and optimization methods on Riemannian manifolds, volume 297. Springer, 1994. Google Scholar
  78. Michele Vergne and Michael Walter. Inequalities for moment cones of finite-dimensional representations. Journal of Symplectic Geometry, 15(4):1209-1250, 2017. URL: https://doi.org/10.4310/JSG.2017.v15.n4.a8.
  79. Frank Verstraete, Jeroen Dehaene, and Bart De Moor. Normal forms and entanglement measures for multipartite quantum states. Physical Review A, 68(1):012103, 2003. URL: https://doi.org/10.1103/PhysRevA.68.012103.
  80. Michael Walter. Multipartite Quantum States and their Marginals. PhD thesis, ETH Zurich, 2014. URL: https://doi.org/10.3929/ethz-a-010250985.
  81. Michael Walter, Brent Doran, David Gross, and Matthias Christandl. Entanglement polytopes: multiparticle entanglement from single-particle information. Science, 340(6137):1205-1208, 2013. URL: https://doi.org/10.1126/science.1232957.
  82. Hongyi Zhang, Sashank J. Reddi, and Suvrit Sra. Fast stochastic optimization on riemannian manifolds. CoRR, abs/1605.07147, 2016. URL: http://arxiv.org/abs/1605.07147.
  83. Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. CoRR, abs/1602.06053, 2016. URL: http://arxiv.org/abs/1602.06053.
  84. Hongyi Zhang and Suvrit Sra. Towards riemannian accelerated gradient methods. CoRR, abs/1806.02812, 2018. URL: http://arxiv.org/abs/1806.02812.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail