Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds

• URL: http://arxiv.org/abs/2609.13646v1
• Date: Sat, 12 Sep 2026 01:53:49 GMT
• Title: Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
• Abstract summary: This work addresses decentralized online convexian optimization on Hadamard.<n>To our knowledge these are the first curvature-independent regret guarantees on embeddings for predicted rates, with no degradation due to curvature.
• Score: 9.035866986287205
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work addresses decentralized online Riemannian optimization on Hadamard manifolds. Prior work under geodesic convexity (g-convexity) may require curvature information in the optimization analysis, typically through a finite lower bound on the sectional curvature. Curvature may also enter the step size or contraction factor of tangent-space Riemannian consensus schemes. In this work, we relax the curvature dependence for a narrower class of horospherical convex (h-convex) functions. We study Distributed Riemannian Online Gradient Descent (D-ROGD), which combines local Riemannian h-subgradient updates with an implicit Fréchet-mean consensus. For h-convex and strongly h-convex local objectives, we establish $O(\sqrt{T})$ and $O(\log T)$ static regret, respectively, matching the corresponding Euclidean rates with respect to $T$, with network dependence governed solely by the spectral gap. To our knowledge, these are the first curvature-independent regret guarantees for decentralized online optimization on Hadamard manifolds. Experiments on hyperbolic embeddings corroborate the predicted rates, with no observable degradation due to curvature.

Related papers

• Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions [9.035866986287205]
  We develop a new type of online optimization for strongly geodesically convex (strongly g-) losses on bounded curved curvature.<n>We prove the first analysis for the two strong-point bandit feedback setting setting the smoothed versions of the bound loss functions.
  arXiv  Detail & Related papers  (2026-07-22T16:03:43Z)
• Distributional Stability of Tangent-Linearized Gaussian Inference on Smooth Manifolds [3.632189127068905]
  We derive explicit non-asymptotic $W$ stability bounds for projection marginalization and surface-measure conditioning.<n>The bounds separate local second-order geometric distortion from nonlocal tail leakage.<n>Experiments validate the predicted calibration transition near $sqrt||_mathrmop/Rapprox 1/6$ and indicate that normal-direction uncertainty is the dominant failure mode when locality breaks.
  arXiv  Detail & Related papers  (2026-02-22T13:18:45Z)
• Riemannian Flow Matching for Disentangled Graph Domain Adaptation [51.98961391065951]
  Graph Domain Adaptation (GDA) typically uses adversarial learning to align graph embeddings in Euclidean space.<n>DisRFM is a geometry-aware GDA framework that unifies embedding and flow-based transport.
  arXiv  Detail & Related papers  (2026-01-31T11:05:35Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives [9.940555460165545]
  We analyze the geodesicity framework (g-ity) for h-in-variants of the curvature manifold.<n>In particular, we investigate the application of a Fr-in-variant with the definite (SPD) with a gradient.
  arXiv  Detail & Related papers  (2025-09-14T12:27:31Z)
• Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds [9.940555460165545]
  We analyze a curvature-aware geodesic step that enables a convergence beyond Hadamard linear distances.<n>We employ gradient, smoothing techniques, and we demonstrate $O(sqrtT)$ regret bound through the same subity analysis.
  arXiv  Detail & Related papers  (2025-09-09T14:14:46Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-max algorithms have been analyzed in the Euclidean setting. We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
  arXiv  Detail & Related papers  (2022-06-04T18:53:44Z)
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces [0.0]
  Research on the acceleration phenomenon on Euclidian curvature by the first global firstorder method. First order method achieves the same rates as in Euclidean gradient as accelerated gradient descent.
  arXiv  Detail & Related papers  (2020-12-07T12:09:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.