Adnan KhanAdnanProduct & AI
San Francisco Bay Area
Get in touch

Source note3 min read

Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions

Source

arXiv

arxiv.org/abs/2607.20316v1

Read the source

Source

Plain-Language Brief

The authors propose a method for decentralized online optimization on Riemannian manifolds with strongly geodesically convex (strongly g-convex) losses, improving upon existing methods that only address g-convex losses. They develop a general network-error analysis for time-varying step sizes and use this to establish an improved static regret bound of O(log T) for decentralized online Riemannian gradient descent, matching the minimax-optimal rate for strongly-convex Euclidean online optimization.

What the Document Says

  • The paper investigates decentralized online optimization for strongly geodesically convex losses on Riemannian manifolds with bounded sectional curvature, including positively curved ones.
  • In centralized Riemannian optimization, strong g-convexity improves the optimal regret from O(sqrt{T}) to O(log T) where T is the time horizon.
  • Existing decentralized methods only address g-convex losses, leaving the strongly g-convex regime unexplored.
  • A challenge is that the required decaying step size in centralized optimization is incompatible with existing network-error analyses that typically assume a fixed step size.
  • The authors provide a general network-error analysis for time-varying schedules.
  • They build on this analysis to establish an O(log T) static regret bound for decentralized online Riemannian gradient descent.
  • This matches the minimax-optimal rate for strongly-convex Euclidean online optimization.

Key Concepts Mentioned

  • Decentralized Online Optimization
  • Riemannian Manifolds
  • Strongly Geodesically Convex Functions
  • Bounded Sectional Curvature
  • Positively Curved Manifolds
  • Optimal Regret
  • Time Horizon
  • Network-Error Analysis
  • Decentralized Riemannian Gradient Descent

Claims Made by the Document

  • Existing methods only address g-convex losses in the decentralized Riemannian setting.
  • The authors provide a general network-error analysis for time-varying schedules.
  • They establish an O(log T) static regret bound for decentralized online Riemannian gradient descent.

Evidence Used

  • The paper proposes a method to address the strongly g-convex regime in the decentralized Riemannian setting.
  • They develop a network-error analysis for time-varying step sizes and use it to establish the static regret bound.

Methods / Approach

UNKNOWN

Limitations Stated by the Authors

  • The authors do not provide an explicit comparison with existing methods in terms of computational complexity and convergence rate.

Limitations Noted by the Agent

Agent interpretation — not from the source.

  • The agent is unable to determine whether the improved regret bound holds for all strongly g-convex functions or just specific types.
  • The agent is unable to predict the practical performance of the proposed method compared to existing methods.

Open Questions

  • What is the computational complexity and convergence rate of the proposed method compared to existing methods?
  • Does the improved regret bound hold for all strongly g-convex functions or just specific types?

Notes for Future Q&A

May include interpretation. Labeled where it does.

  • The paper does not explicitly state whether the improved regret bound holds for all strongly g-convex functions or just specific types.
  • It's unclear how the proposed method performs compared to existing methods in terms of computational complexity and convergence rate.

Raw Abstract / Excerpt

We study decentralized online optimization for strongly geodesically convex (strongly g-convex) losses on Riemannian manifolds with bounded sectional curvature, including positively curved manifolds. In centralized Riemannian optimization, strong g-convexity tightens the optimal regret from $O(\sqrt{T})$ to $O(\log T)$, where $T$ is the time horizon; in the decentralized Riemannian setting, however, existing methods address only g-convex losses, leaving the strongly g-convex regime unexplored. One challenge is that the required decaying step size in the centralized regime is incompatible with existing network-error analyses, which typically assume a fixed step size. First, we provide a general network-error analysis for time-varying schedules. Next, we build on this analysis to establish the first $O(\log T)$ static regret bound for decentralized online Riemannian gradient descent, matching the minimax-optimal rate for strongly-convex Euclidean online optimization. Finally, we prove the same $O(\log T)$ regret bound for the two-point bandit feedback setting using novel strong subconvexity arguments for the smoothed versions of the loss functions.