Document Open Access Logo

Barriers for Recent Methods in Geodesic Optimization

Authors W. Cole Franks , Philipp Reichenbach

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.13.pdf
  • Filesize: 1.2 MB
  • 54 pages

Document Identifiers

Author Details

W. Cole Franks
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA
Philipp Reichenbach
  • Institut für Mathematik, Technische Universität Berlin, Germany

Funding

  • Reichenbach, Philipp: acknowledges funding by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. 787840).

Acknowledgements

The authors thank Jason Altschuler, Peter Bürgisser, Visu Makam, Adam Sawicki and Michael Walter for helpful discussions. Furthermore, the authors thank the anonymous referees for helpful comments and suggestions.

Cite AsGet BibTex

W. Cole Franks and Philipp Reichenbach. Barriers for Recent Methods in Geodesic Optimization. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 13:1-13:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CCC.2021.13

Abstract

We study a class of optimization problems including matrix scaling, matrix balancing, multidimensional array scaling, operator scaling, and tensor scaling that arise frequently in theory and in practice. Some of these problems, such as matrix and array scaling, are convex in the Euclidean sense, but others such as operator scaling and tensor scaling are geodesically convex on a different Riemannian manifold. Trust region methods, which include box-constrained Newton’s method, are known to produce high precision solutions very quickly for matrix scaling and matrix balancing (Cohen et. al., FOCS 2017, Allen-Zhu et. al. FOCS 2017), and result in polynomial time algorithms for some geodesically convex problems like operator scaling (Garg et. al. STOC 2018, Bürgisser et. al. FOCS 2019). One is led to ask whether these guarantees also hold for multidimensional array scaling and tensor scaling. We show that this is not the case by exhibiting instances with exponential diameter bound: we construct polynomial-size instances of 3-dimensional array scaling and 3-tensor scaling whose approximate solutions all have doubly exponential condition number. Moreover, we study convex-geometric notions of complexity known as margin and gap, which are used to bound the running times of all existing optimization algorithms for such problems. We show that margin and gap are exponentially small for several problems including array scaling, tensor scaling and polynomial scaling. Our results suggest that it is impossible to prove polynomial running time bounds for tensor scaling based on diameter bounds alone. Therefore, our work motivates the search for analogues of more sophisticated algorithms, such as interior point methods, for geodesically convex optimization that do not rely on polynomial diameter bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Continuous optimization
  • Mathematics of computing → Combinatorics
Keywords
  • Geodesically Convex Optimization
  • Weight Margin
  • Moment Polytope
  • Diameter Bounds
  • Tensor Scaling
  • Matrix Scaling

Metrics

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

Related Versions

References

  1. P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, Princeton, NJ, 2008. With a foreword by Paul Van Dooren. URL: https://doi.org/10.1515/9781400830244.
  2. Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 172-181, 2018. Google Scholar
  3. Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 890-901. IEEE, 2017. Google Scholar
  4. Noga Alon and Văn H. Vũ. Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs. Journal of Combinatorial Theory, Series A, 79(1):133-160, 1997. Google Scholar
  5. Jason M. Altschuler and Enric Boix-Adsera. Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure, 2020. URL: http://arxiv.org/abs/2008.03006.
  6. 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.
  7. Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 35-46. IEEE, 2018. Google Scholar
  8. Miroslav Bacák. Convex analysis and optimization in Hadamard spaces, volume 22. Walter de Gruyter GmbH & Co KG, 2014. Google Scholar
  9. Rajendra Bhatia. Positive definite matrices. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2007. Google Scholar
  10. 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.
  11. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 883-897. IEEE, 2018. Google Scholar
  12. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes, 2019. URL: http://arxiv.org/abs/1910.12375.
  13. Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1-24:20, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.24.
  14. 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.
  15. James W. Cannon, William J. Floyd, Richard Kenyon, Walter R. Parry, et al. Hyperbolic geometry. Flavors of geometry, 31:59-115, 1997. Google Scholar
  16. 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 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 902-913. IEEE, 2017. Google Scholar
  17. Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in neural information processing systems, pages 2292-2300, 2013. Google Scholar
  18. Jiri Dadok and Victor Kac. Polar representations. J. Algebra, 92(2):504-524, 1985. URL: https://doi.org/10.1016/0021-8693(85)90136-X.
  19. Harm Derksen and Visu Makam. Degree bounds for semi-invariant rings of quivers. J. Pure Appl. Algebra, 222(10):3282-3292, 2018. URL: https://doi.org/10.1016/j.jpaa.2017.12.007.
  20. Harm Derksen and Visu Makam. Algorithms for orbit closure separation for invariants and semi-invariants of matrices. Algebra Number Theory, 14(10):2791-2813, 2020. URL: https://doi.org/10.2140/ant.2020.14.2791.
  21. Harm Derksen and Visu Makam. An exponential lower bound for the degrees of invariants of cubic forms and tensor actions. Adv. Math., 368:107136, 25, 2020. URL: https://doi.org/10.1016/j.aim.2020.107136.
  22. Michael A Forbes and Amir Shpilka. Explicit noether normalization for simultaneous conjugation via polynomial identity testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 527-542. Springer, 2013. Google Scholar
  23. Cole Franks and Ankur Moitra. Rigorous Guarantees for Tyler’s M-estimator via quantum expansion, 2020. URL: http://arxiv.org/abs/2002.00071.
  24. Matthias Franz. Moment polytopes of projective G-varieties and tensor products of symmetric group representations. J. Lie Theory, 12(2):539-549, 2002. Google Scholar
  25. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 109-117. IEEE, 2016. Google Scholar
  26. Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson. Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. In 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:17, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.12.
  27. X. Gual-Arnau and A. M. Naveira. Volume of tubes in noncompact symmetric spaces. Publ. Math. Debrecen, 54(3-4):313-320, 1999. Google Scholar
  28. V. Guillemin and S. Sternberg. Convexity properties of the moment mapping. II. Invent. Math., 77(3):533-546, 1984. URL: https://doi.org/10.1007/BF01388837.
  29. Leonid Gurvits. Classical complexity and quantum entanglement. Journal of Computer and System Sciences, 69(3):448-484, 2004. Google Scholar
  30. Leonid Gurvits. Combinatorial and algorithmic aspects of hyperbolic polynomials, 2004. URL: http://arxiv.org/abs/math/0404474.
  31. Brian C. Hall. Lie groups, Lie algebras, and representations, volume 222 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2003. An elementary introduction. URL: https://doi.org/10.1007/978-0-387-21554-9.
  32. Linus Hamilton and Ankur Moitra. No-go Theorem for Acceleration in the Hyperbolic Plane, 2021. URL: http://arxiv.org/abs/2101.05657.
  33. Moritz Hardt and Ankur Moitra. Algorithms and hardness for robust subspace recovery. In Conference on Learning Theory, pages 354-375, 2013. Google Scholar
  34. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Constructive non-commutative rank computation is in deterministic polynomial time. Comput. Complexity, 27(4):561-593, 2018. URL: https://doi.org/10.1007/s00037-018-0165-7.
  35. Bahman Kalantari and Leonid Khachiyan. On the complexity of nonnegative-matrix scaling. Linear Algebra and its applications, 240:87-103, 1996. Google Scholar
  36. George Kempf and Linda Ness. The length of vectors in representation spaces. In Algebraic geometry (Proc. Summer Meeting, Univ. Copenhagen, Copenhagen, 1978), volume 732 of Lecture Notes in Math., pages 233-243. Springer, Berlin, 1979. Google Scholar
  37. M. K. Kravtsov and V. E. Lukshin. On some properties of noninteger vertices of a three-index axial transportation polytope. Tr. Inst. Matematiki NAN Belarusi, 13(2):31-36, 2005. Google Scholar
  38. V. M. Kravtsov. Combinatorial properties of noninteger vertices of a polytope in a three-index axial assignment problem. Kibernet. Sistem. Anal., 43(1):33-44, 189, 2007. URL: https://doi.org/10.1007/s10559-007-0023-0.
  39. Tianyi Lin, Nhat Ho, Marco Cuturi, and Michael I. Jordan. On the complexity of approximating multimarginal optimal transport, 2019. URL: http://arxiv.org/abs/1910.00152.
  40. Nathan Linial and Zur Luria. On the vertices of the d-dimensional Birkhoff polytope. Discrete & Computational Geometry, 51(1):161-170, 2014. Google Scholar
  41. Tomasz Maciążek and Adam Sawicki. Critical points of the linear entropy for pure L-qubit states. Journal of Physics A: Mathematical and Theoretical, 48(4):045305, January 2015. URL: https://doi.org/10.1088/1751-8113/48/4/045305.
  42. Tomasz Maciążek and Adam Sawicki. Asymptotic properties of entanglement polytopes for large number of qubits. Journal of Physics A: Mathematical and Theoretical, 51(7):07LT01, January 2018. URL: https://doi.org/10.1088/1751-8121/aaa4d7.
  43. Ketan Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. Journal of the American Mathematical Society, 30(1):225-309, 2017. Google Scholar
  44. David Mumford. Geometric Invariant Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete, Neue Folge, Band 34. Springer-Verlag, Berlin-New York, 1965. Google Scholar
  45. Linda Ness. A stratification of the null cone via the moment map. Amer. J. Math., 106(6):1281-1329, 1984. With an appendix by David Mumford. URL: https://doi.org/10.2307/2374395.
  46. Beresford N. Parlett and Christian Reinsch. Balancing a matrix for calculation of eigenvalues and eigenvectors. In Handbook for Automatic Computation, pages 315-326. Springer, 1971. Google Scholar
  47. Alexander Rusciano. A Riemannian Corollary of Helly’s theorem. J. Convex Anal., 27(4):1261-1275, 2020. Google Scholar
  48. Mohit Singh and Nisheeth K. Vishnoi. Entropy, optimization and counting. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 50-59, 2014. Google Scholar
  49. Reyer Sjamaar. Convexity properties of the moment mapping re-examined. Adv. Math., 138(1):46-91, 1998. URL: https://doi.org/10.1006/aima.1998.1739.
  50. Damian Straszak and Nisheeth K. Vishnoi. Maximum entropy distributions: Bit complexity and stability. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2861-2891. PMLR, 25-28 June 2019. URL: http://arxiv.org/abs/1711.02036.
  51. Nolan R. Wallach. Geometric Invariant Theory: Over the real and complex numbers. Universitext. Springer, Cham, 2017. URL: https://doi.org/10.1007/978-3-319-65907-7.
  52. Hermann Weyl. The classical groups: their invariants and representations, volume 45. Princeton university press, 1946. Google Scholar
  53. Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference on Learning Theory, pages 1617-1638. PMLR, 2016. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact