2 Search Results for "Reichenbach, Philipp"

Document
DOI: 10.4230/LIPIcs.CCC.2021.13
Barriers for Recent Methods in Geodesic Optimization

Authors: W. Cole Franks and Philipp Reichenbach

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{franks_et_al:LIPIcs.CCC.2021.13,
  author =	{Franks, W. Cole and Reichenbach, Philipp},
  title =	{{Barriers for Recent Methods in Geodesic Optimization}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{13:1--13:54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.13},
  URN =		{urn:nbn:de:0030-drops-142879},
  doi =		{10.4230/LIPIcs.CCC.2021.13},
  annote =	{Keywords: Geodesically Convex Optimization, Weight Margin, Moment Polytope, Diameter Bounds, Tensor Scaling, Matrix Scaling}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2021.1
Optimization, Complexity and Invariant Theory (Invited Talk)

Authors: Peter Bürgisser

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{burgisser:LIPIcs.STACS.2021.1,
  author =	{B\"{u}rgisser, Peter},
  title =	{{Optimization, Complexity and Invariant Theory}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.1},
  URN =		{urn:nbn:de:0030-drops-136460},
  doi =		{10.4230/LIPIcs.STACS.2021.1},
  annote =	{Keywords: geometric invariant theory, geodesic optimization, non-commutative optimization, null cone, operator scaling, moment polytope, orbit closure intersection, geometric programming}
}
  • Refine by Author
  • 1 Bürgisser, Peter
  • 1 Franks, W. Cole
  • 1 Reichenbach, Philipp

  • Refine by Classification
  • 2 Theory of computation → Continuous optimization
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Algebraic complexity theory

  • Refine by Keyword
  • 1 Diameter Bounds
  • 1 Geodesically Convex Optimization
  • 1 Matrix Scaling
  • 1 Moment Polytope
  • 1 Tensor Scaling
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2021

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