Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912958799413248 |
|---|---|
| author | Goodwin, Ariel Lewis, Adrian S. López-Acedo, Genaro Nicolae, Adriana |
| author_facet | Goodwin, Ariel Lewis, Adrian S. López-Acedo, Genaro Nicolae, Adriana |
| contents | As a foundation for optimization, convexity is useful beyond the classical settings of Euclidean and Hilbert space. The broader arena of nonpositively curved metric spaces, which includes manifolds like hyperbolic space, as well as metric trees and more general CAT(0) cubical complexes, supports primal tools like proximal operations for geodesically convex functions. However, the lack of linear structure in such spaces complicates dual constructions like subgradients. To address this hurdle, we introduce a new type of subgradient for functions on Hadamard spaces, based on Busemann functions. Our notion supports generalizations of classical stochastic and incremental subgradient methods, with guaranteed complexity bounds. We illustrate with subgradient algorithms for $p$-mean problems in general Hadamard spaces, in particular computing medians in BHV tree space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_06730 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces Goodwin, Ariel Lewis, Adrian S. López-Acedo, Genaro Nicolae, Adriana Optimization and Control Computational Geometry Data Structures and Algorithms Numerical Analysis 90C48, 65Y20, 49M29 G.1.6 As a foundation for optimization, convexity is useful beyond the classical settings of Euclidean and Hilbert space. The broader arena of nonpositively curved metric spaces, which includes manifolds like hyperbolic space, as well as metric trees and more general CAT(0) cubical complexes, supports primal tools like proximal operations for geodesically convex functions. However, the lack of linear structure in such spaces complicates dual constructions like subgradients. To address this hurdle, we introduce a new type of subgradient for functions on Hadamard spaces, based on Busemann functions. Our notion supports generalizations of classical stochastic and incremental subgradient methods, with guaranteed complexity bounds. We illustrate with subgradient algorithms for $p$-mean problems in general Hadamard spaces, in particular computing medians in BHV tree space. |
| title | Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces |
| topic | Optimization and Control Computational Geometry Data Structures and Algorithms Numerical Analysis 90C48, 65Y20, 49M29 G.1.6 |
| url | https://arxiv.org/abs/2412.06730 |