Gradient Descent for Unbounded Convex Functions on Hadamard Manifolds and Its Applications to Scaling Problems

References

• [1] Allen-Zhu Z, Garg A, Li Y, Oliveira R, Wigderson A (2018) Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. Diakonikolas I, Kempe D, eds. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. STOC 2018 (Association for Computing Machinery, New York), 172–181.Google Scholar
• [2] Alvarez F, Bolte J, Brahic O (2004) Hessian Riemannian gradient flows in convex programming. SIAM J. Control Optim. 43(2):477–501.Crossref, Google Scholar
• [3] Ambrosio L, Gigli N, Savaré G (2008) Gradient Flows: In Metric Spaces and in the Space of Probability Measures, 2nd ed. (Birkhäuser, Basel, Switzerland).Google Scholar
• [4] Auslender A (1997) How to deal with the unbounded in optimization: Theory and algorithms. Math. Programming 79(1–3):3–18.Crossref, Google Scholar
• [5] Bačák M (2014) Convex Analysis and Optimization in Hadamard Spaces (De Gruyter, Berlin).Crossref, Google Scholar
• [6] Beck A (2017) First-Order Methods in Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [7] Berger T, Trenn S (2012) The quasi-Kronecker form for matrix pencils. SIAM J. Matrix Anal. Appl. 33(2):336–368.Crossref, Google Scholar
• [8] Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [9] Bridson MR, Haefliger A (1999) Metric Spaces of Non-Positive Curvature (Springer-Verlag, Berlin).Crossref, Google Scholar
• [10] Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3–4):231–357.Crossref, Google Scholar
• [11] Bürgisser P, Li Y, Nieuwboer H, Walter M (2020) Interior-point methods for unconstrained geometric programming and scaling problems. Preprint, submitted August 27, https://arxiv.org/abs/2008.12110.Google Scholar
• [12] Bürgisser P, Franks C, Garg A, Oliveira R, Walter M, Wigderson A (2018) Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. Thorup M, ed. Proc. 59th IEEE Annual Sympos. Foundations Comput. Sci. FOCS 2018 (IEEE, New York), 883–897.Google Scholar
• [13] Bürgisser P, Franks C, Garg A, Oliveira R, Walter M, Wigderson A (2019) Towards a theory of non-commutative optimization: Geodesic 1st and 2nd order methods for moment maps and polytopes. Proc. 60th IEEE Annual Sympos. Foundations Comput. Sci. FOCS 2019 (IEEE, New York), 845–861.Google Scholar
• [14] Caprace P-E, Lytchak A (2010) At infinity of finite-dimensional CAT(0) spaces. Math. Ann. 346(1):1–21.Crossref, Google Scholar
• [15] Chen X, Sun S (2014) Calabi flow, geodesic rays, and uniqueness of constant scalar curvature Kähler metrics. Ann. Math. 180(2):407–454.Crossref, Google Scholar
• [16] Demmel J, Kåragström B (1993) The generalized Schur decomposition of an arbitrary pencil A−λB—Robust software with error bounds and applications. I. Theory and algorithms. ACM Trans. Math. Software 19(2):160–174.Crossref, Google Scholar
• [17] Dulmage AL, Mendelsohn NS (1958) Coverings of bipartite graphs. Canadian J. Math. 10:517–534.Crossref, Google Scholar
• [18] Franks C (2018) Operator scaling with specified marginals. Diakonikolas I, Kempe D, eds. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (STOC 2018) (Association for Computing Machinery, New York). 190–203.Google Scholar
• [19] Franks C, Soma T, Goemans MX (2023) Shrunk subspaces via operator Sinkhorn iteration. Bansal N, Nagarajan V, eds. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1655–1668.Google Scholar
• [20] Gantmacher FR (1959) The Theory of Matrices, vol. 1–2 (Chelsea Publishing Co., New York).Google Scholar
• [21] Garg A, Oliveira R (2018) Recent progress on scaling algorithms and applications. Bull. Eur. Assoc. Theoret. Comput. Sci. (125):14–49.Google Scholar
• [22] Garg A, Gurvits L, Oliveira R, Wigderson A (2018) Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. Geometric Funct. Anal. 28(1):100–145.Crossref, Google Scholar
• [23] Garg A, Gurvits L, Oliveira R, Wigderson A (2020) Operator scaling: Theory and applications. Foundations Comput. Math. 20(2):223–290.Crossref, Google Scholar
• [24] Georgoulas V, Robbin JW, Salamon DA (2021) The Moment-Weight Inequality and the Hilbert-Mumford Criterion—GIT from the Differential Geometric Viewpoint, Lecture Notes in Mathematics, vol. 2297 (Springer, Cham, Switzerland).Google Scholar
• [25] Guillemin V, Sternberg S (1982) Convexity properties of the moment mapping. Inventiones Math. 67(3):491–513.Crossref, Google Scholar
• [26] Guillemin V, Sternberg S (1984) Convexity properties of the moment mapping. II. Inventiones Math. 77(3):533–546.Crossref, Google Scholar
• [27] Gurvits L (2004) Classical complexity and quantum entanglement. J. Comput. System Sci. 69(3):448–484.Crossref, Google Scholar
• [28] Hamada M, Hirai H (2021) Computing the nc-rank via discrete convex optimization on CAT(0) spaces. SIAM J. Appl. Algebra Geometry 5(3):455–478.Crossref, Google Scholar
• [29] Hayashi K, Hirai H, Sakabe K (2023) Finding Hall blockers by matrix scaling. Math. Oper. Res. 49(4):2166–2179.Link, Google Scholar
• [30] Hirai H (2024) Convex analysis on Hadamard spaces and scaling problems. Foundations Comput. Math. 24(6):1979–2016.Crossref, Google Scholar
• [31] Hirai H (2025) Generalized gradient flows in Hadamard manifolds and convex optimization on entanglement polytopes. Preprint, submitted November 15, https://arxiv.org/abs/2511.12064v1.Google Scholar
• [32] Hirai H (2026) A scaling characterization of nc-rank via unbounded gradient flow. Linear Algebra Appl. 730:525–545.Crossref, Google Scholar
• [33] Hirai H, Sakabe K (2024) Gradient descent for unbounded convex functions on Hadamard manifolds and its applications to scaling problems. Proc. 65th IEEE Sympos. Foundations Comput. Sci. (FOCS 2024) (IEEE, New York), 2387–2402.Google Scholar
• [34] Hirai H, Nieuwboer H, Walter M (2023) Interior-point methods on manifolds: Theory and applications. Proc. 64th IEEE Sympos. Foundations Comput. Sci. (FOCS 2023) (IEEE, New York), 2021–2030.Google Scholar
• [35] Hiriart-Urruty J-B, Lemaréchal C (2001) Fundamentals of Convex Analysis (Springer-Verlag, Berlin).Crossref, Google Scholar
• [36] Ito H, Iwata S, Murota K (1994) Block-triangularizations of partitioned matrices under similarity/equivalence transformations. SIAM J. Matrix Anal. Appl. 15(4):1226–1255.Crossref, Google Scholar
• [37] Ivanyos G, Qiao Y, Subrahmanyam KV (2017) Non-commutative Edmonds’ problem and matrix semi-invariants. Comput. Complexity 26(3):717–763.Crossref, Google Scholar
• [38] Ivanyos G, Qiao Y, Subrahmanyam KV (2018) Constructive non-commutative rank computation is in deterministic polynomial time. Comput. Complexity 27(4):561–593.Crossref, Google Scholar
• [39] Iwamasa Y, Oki T, Soma T (2025) Algorithmic aspects of semistability of quiver representations. Censor-Hillel K, Grandoni F, Ouaknine J, Puppis G, eds. 52nd Internat. Colloquium Automata Languages Programming (ICALP 2025) (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 99:1–99:18.Google Scholar
• [40] Kapovich M, Leeb B, Millson J (2009) Convex functions on symmetric spaces, side lengths of polygons and the stability inequalities for weighted configurations at infinity. J. Differential Geometry 81(2):297–354.Crossref, Google Scholar
• [41] Karlsson A, Margulis GA (1999) A multiplicative ergodic theorem and nonpositively curved spaces. Comm. Math. Phys. 208(1):107–123.Crossref, Google Scholar
• [42] Kempf GR (1978) Instability in invariant theory. Ann. Math. 108(2):299–316.Crossref, Google Scholar
• [43] Kirwan F (1984) Convexity properties of the moment mapping. III. Inventiones Math. 77(3):547–552.Crossref, Google Scholar
• [44] Kleiner B, Leeb B (2006) Rigidity of invariant convex sets in symmetric spaces. Inventiones Math. 163(3):657–676.Crossref, Google Scholar
• [45] Kwok TC, Lau LC, Ramachandran A (2021) Spectral analysis of matrix scaling and operator scaling. SIAM J. Comput. 50(3):1034–1102.Crossref, Google Scholar
• [46] Lu H, Freund RM, Nesterov Y (2018) Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim. 28(1):333–354.Crossref, Google Scholar
• [47] Mayer UF (1998) Gradient flows on nonpositively curved metric spaces and harmonic maps. Comm. Anal. Geometry 6(2):199–253.Crossref, Google Scholar
• [48] Murota K (2000) Matrices and Matroids for Systems Analysis (Springer-Verlag, Berlin).Google Scholar
• [49] Nemirovsky AS, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization (John Wiley & Sons, Inc., New York).Google Scholar
• [50] Obuchowska WT (2004) On the minimizing trajectory of convex functions with unbounded level sets. Comput. Optim. Appl. 27(1):37–52.Crossref, Google Scholar
• [51] Ohta S (2025) Discrete-time gradient flows for unbounded convex functions on Gromov hyperbolic spaces. Comm. Contemporary Math., ePub ahead of print December 11, https://doi.org/10.1142/S0219199726500033.Crossref, Google Scholar
• [52] Ohta S, Pálfia M (2015) Discrete-time gradient flows and law of large numbers in Alexandrov spaces. Calculus Variations Partial Differential Equations 54(2):1591–1610.Crossref, Google Scholar
• [53] Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [54] Sakabe K (2026) Nesterov’s accelerated gradient for unbounded convex functions finds the minimum-norm point in the dual space. Preprint, submitted February 9, https://arxiv.org/abs/2602.08618.Google Scholar
• [55] Sakabe K, Doğan ML, Walter M (2026) Strassen’s support functionals coincide with the quantum functionals. Preprint, submitted January 29, https://arxiv.org/abs/2601.21553.Google Scholar
• [56] Sakai T (1996) Riemannian Geometry (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [57] Sanz Serna JM, Zygalakis KC (2020) Contractivity of Runge-Kutta methods for convex gradient systems. SIAM J. Numer. Anal. 58(4):2079–2092.Crossref, Google Scholar
• [58] Sinkhorn R (1964) A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist. 35(2):876–879.Crossref, Google Scholar
• [59] Van Dooren P (1979) The computation of Kronecker’s canonical form of a singular pencil. Linear Algebra Appl. 27:103–140.Crossref, Google Scholar
• [60] Vishnoi NK (2021) Algorithms for Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [61] Wallach NR (2017) Geometric Invariant Theory (Springer, Cham, Switzerland).Crossref, Google Scholar
• [62] Woodward CT (2011) Moment maps and geometric invariant theory. Preprint, submitted June 29, https://arxiv.org/abs/0912.1132.Google Scholar