Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces

• 成果类型: Article; Early Access
• 署名作者: Goodwin, Ariel; Lewis, Adrian S.; Lopez-Acedo, Genaro; Nicolae, Adriana
• 署名单位: Cornell University; Cornell University; Babes Bolyai University from Cluj
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02334-4
• 发表日期: 2026-03-04
• 关键词: Convex optimization; subgradient; Hadamard space; splitting; complexity; Busemann Function; Mean; median; Tree space; algorithm

摘要

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.